1. Field of the Invention
The present invention relates to network protocols and to network intermediate devices executing such protocols; and more particularly, to algorithms for managing a tree of network devices for a data network according to a spanning tree protocol.
2. Description of Related Art
Local area networks (xe2x80x9cLANsxe2x80x9d) specified according to Institute of Electrical Electronic Engineers (xe2x80x9cIEEExe2x80x9d) Standards for Local and Metropolitan Area Networks under section 802.x of all types may be connected together by media access control (xe2x80x9cMACxe2x80x9d) bridges. MAC Bridges interconnect LAN segments so that stations connected to the LANs operate as if they were attached to a single LAN for many purposes. Thus a bridged LAN provides for the interconnection of stations attached to LAN segments of different MAC types, for an increase in the physical extent, for the number of permissible attachments and the total performance of a LAN, and for the partitioning of physical LAN support for administrative or maintenance reasons. The MAC bridge is specified according to the IEEE standard 802.1D (IEEE Std. 802.1D-1990, IEEE Standards for Local and Metropolitan Area Networks: Media Access Control (MAC) Bridges.)
When a bridged network is established, it is possible to create loops in the network by providing more than one path through bridges and LAN segments between two points. Thus, according to the 802.1D standard, an active topology for the bridged network is maintained according to the spanning tree protocol which is described in the standard. The spanning tree protocol automatically establishes a fully connected (spanning) and a loop-free (tree) bridged network topology. It uses a distributed algorithm that selects a root bridge and the shortest path to that root from each LAN. Tie breakers are used to ensure that there is a unique shortest path to the root, while the uniqueness of the root is guaranteed by using one of its MAC addresses as part of a priority identifier.
Every LAN in the network has one and only one xe2x80x9cdesignated portxe2x80x9d providing the shortest path to the root for that LAN, through the bridge of which the designated port is a part. The bridge is known as the xe2x80x9cdesignated bridgexe2x80x9d for that LAN.
Thus, bridges other than the root bridge at the root of the network can be termed a branch bridge. Every branch bridge has a xe2x80x9croot portxe2x80x9d which is the port providing the shortest path to the root for that bridge. Ports other than the root port are designated ports, or alternate ports, according to the standard. An alternate port is connected to a LAN for which another bridge is the designated bridge, and is placed into a blocking state so that frames are not forwarded through that port.
Thus, the frame forwarding path through any bridge is between its root port and its designated ports. When spanning tree information has been completely distributed and is stable, this connectivity will connect all of the LANs in a loop-free tree.
When a bridge first receives spanning tree information that dictates new connectivity through that bridge, it does not establish the new connectivity immediately. Ports that were previously connected as either the root port or as a designated port, but are no longer in the forwarding state, are immediately made blocking. However, the transition to a forwarding state of ports that were previously not connected in a forwarding role is delayed. The delay serves two purposes:
(1) Frames forwarded on the previous topology may still be buffered by bridges in the network. Thus, an instantaneous bridge to the new topology can cause these frames to be forwarded back to their LAN of origin, causing duplication of the frame once; and
(2) New spanning tree information in the network may not have been fully distributed yet. Thus an immediate change to a new topology may cause temporary loops. These loops could generate high traffic volumes, disrupting end stations, causing frame loss in bridges, and possibly delaying the propagation of spanning tree information further.
According to the spanning tree protocol of the standard, each port on a bridge can assume a blocking state in which frames are not forwarded through the port, and a forwarding state in which frames are forwarded through the port. For a transition from the blocking state to the forwarding state, the protocol requires the port to proceed through transitional states referred to as the listening state and the learning state.
In the listening state, the port is preparing to participate in frame relay; however, frame relay is temporarily disabled to prevent temporary loops. In the listening state, the port monitors bridge protocol data unit (xe2x80x9cBPDUxe2x80x9d) frames or other information related to the topology in the network for an interval referred to as the forward delay timer. If no information is received which causes a change in state of the port before expiry of the forward delay timer, then the port transitions to the learning state.
In the learning state, the port continues to prepare for participation in frame relay. The relay is temporarily disabled to prevent loops. In this state, in addition to monitoring the BPDU frames and other information related to the operation of the spanning tree algorithm, the port learns information about end stations that are accessible through the port for use in the forwarding of frames once the frame enters the forwarding state. Upon expiration of the forward delay timer in the learning state, if no better information about the protocol is received, then the port assumes the forwarding state. Thus, the transition from a blocking state to the forwarding state takes two times the forward delay timer interval. A significant amount of time may pass from the time of detection of a change in topology causing a transition from the blocking state to the forwarding state, until the time in which the forwarding state is assumed. This time may be as long as 20 to 50 seconds in some cases.
Convergence of a bridged network in situations involving changing of spanning tree topology can therefore cause significant loss of service situations, particularly in networks that carry real time data. For example, the use of data networks and the Internet for audio and video transmissions of real time signals is increasing. Twenty to fifty second convergence times for these uses of the data network can cause unacceptable glitches. Accordingly, it is desirable to provide a technique to improve the availability of a bridged network in the face of changes in topology.
Work is being done in the Institute of Electrical Electronic Engineers (xe2x80x9cIEEExe2x80x9d) 802.1 working group to speed up the convergence of the spanning tree in the face of topology changes. One such proposal converts an alternate port to the root port of the bridge if the original root port fails. An alternate port on a bridge is connected to a segment on another path to be root bridge. According to the proposals, addresses are also transferred from the failed root port to the new root port. The new root port goes into a forwarding state immediately after the transition. This process is described in our previous U.S. patent application Ser. No. 09/141,803 which is incorporated by reference above.
An alternate port on a bridge has information about the designated bridge/port and the designated cost on the segment to which it is connected. When the alternate port assumes the root port role, BPDUs are sent by the bridge with information indicating the change. The spanning tree proposal also requires downstream bridges to accept inferior information from a designated bridge. Since an alternate port is chosen as the root port, the new information will be inferior to the previously held information. When the changing bridge advertises the inferior information on its designated ports, downstream bridges receive this information and calculate the report and root path cost using. As a result of the calculation, downstream bridges either remain attached to the original root port, or find an alternate and better root port. The new and inferior information is then propagated downstream until all the downstream bridges have seen the change and the spanning tree converges.
However, selecting an arbitrary alternate port as the root port in response to new path cost information received from an upstream bridge can result in loops in some topologies. For example, such loops may occur in the topologies shown in FIG. 1A and FIG. 1B. In this topology, root bridge S1 has a first designated port connected to a corresponding root port on bridge S2 and a second designated port connected to a corresponding root port on bridge S3. Bridge S3 has designated ports connected to a corresponding root port on bridge S4 and to a corresponding alternate port on bridge S6. Bridge S4 has a designated port coupled to bridge S6. On the other branch, bridge S3 has designated ports connected to bridges S5, S2, and S4. Bridges S2 and S4 have alternate ports coupled to corresponding designated ports on bridge S3. Bridge S6 has an alternate port coupled to the corresponding designated port on bridge S2. In the scenario shown in FIG. 1A, if the root port on bridge S2 fails, the alternate port connected to bridge S3 will transition to the root port role. Assuming that the path between bridge S3 and the original root port S1 is high, the bridge S2 will then begin propagating the path cost information which will appear inferior at bridges S4 and S6. Other events can also cause inferior information to be propagated down this branch of the tree. Because the path through bridge S4 to bridge S6 may be fast, there is the potential that the inferior information will be received on the alternate port of bridge S6. Because the path cost through the alternate port on bridge S6 will not reflect the failure, the inferior information received on the root port of bridge S6 could cause the bridge to change from its previously alternate port into the root port role and from its previously root port into the designated port role. In this case, bridge S6 will begin propagating information to bridge S4 and S2 through the previously root port, now in the designated port role. As shown in FIG. 1B, the previously designated ports on bridges S2 and S4 can transition to the root port role in response to the information received from bridge S6, if the information from S6 is better than the information received from bridge S2. This sequence of events would create a loop among bridges S2, S4 and S6. The injected information would loop among these bridges with increased root cost and message age in each hop, until one of the bridges finds an alternate port providing better information outside the loop. For example, the alternate port on bridge S4 could receive information from bridge S3 to break the loop. Alternatively, the message age time could exceed the maximum value causing a new root port selection to break the loop. However, the data path which would cause this loop will not open in the prior art, because the transition from root port to designate port invokes a waiting interval during this convergence. However, during the convergence, the bridges do not forward packets. When the convergence timer has expired, the topology will normally converge in the existing standard spanning tree, preventing loops.
Accordingly, it is desirable to provide a method that identifies appropriate alternate ports which are good candidates for becoming the root port without forming a loop, while allowing for a more rapid convergence of the spanning tree.
The present invention provides techniques to select an alternate port in a manner that prevents loops, and allows immediate transition of a previously root port to the designated port role.
Thus, the present invention can be characterized as an improvement to the spanning tree protocol which provides for identifying a port on the bridge in the alternate port role which qualifies as a candidate root port. Upon the receipt of changed path cost information, or other events causing a selection of a new root port, the candidate root port transitions to the root port role and forwarding state immediately, without traversing the listening and learning states of the standard protocol and without requiring satisfaction of the conditions of such transitional states. Also, the previously root port may transition into the designated port role without wait states, which allows rapid, loop-free convergence of the spanning tree.
The present invention provides the mechanisms to identify alternate ports, termed xe2x80x9ccandidate root portsxe2x80x9d herein, that are candidates for becoming the root ports in the event of a topology change. Not all of the alternate ports on a bridge can serve as the root port in an arbitrary spanning topology. Because some alternate ports are connected to segments that might lead to loops, such loops result in the xe2x80x9ccounting to infinityxe2x80x9d problem as is well known in the routing world (Routing Information Protocol or xe2x80x9cRIPxe2x80x9d). Methods are provided to identify ports in a candidate root role alternate ports that lead to loop-free alternate paths to the root bridge. When a root port selection process causes the root port on a bridge to change, one of the selected candidate root ports (the one with the least root path cost) can be selected as the root port and the modified spanning tree algorithms speed up the convergence and reduce address learning.
According to the present invention, qualification as a suitable candidate root port is based upon propagating a message from the root bridge, such as a bridge protocol data unit (xe2x80x9cBPDUxe2x80x9d) message, carrying the identifier of the port on the root bridge from which the message originates. For the standard spanning tree protocol, the port identifier from the root bridge is provided in addition to the identifier of the port of the bridge from which the BPDU is received. Logic in the bridges is able to identify the branch of the tree from which the message originates, and to select the candidate root port in response to the branch information. Thus, a port on a different branch than the root is a suitable candidate root port. A port on the same branch as the root is suitable if it has recently received (such as within one Hello time in the standard spanning tree) updated configuration information from its upstream bridge (designated bridge on the port), such as by a configuration BPDU. If it has not received recent configuration information, then the alternate port can provoke a new BPDU, such as by sending inferior information on the affected segment which causes the upstream bridge to respond with better information.
Downstream bridges that are not acting according to the protocol (i.e., misbehaving bridges) may also cause loop conditions. Techniques are provided to detect a misbehaving downstream bridge. In a first technique, the configuration BPDU is enhanced to include a hop count from the root bridge. If an alternate port receives a BPDU with a lower hop count than the root port is receiving, then the alternate port is a suitable candidate root port. In an alternative approach, an alternate port is a suitable candidate root port if the MAC address of the designated bridge on the alternate port has been learned on the root port on the bridge.
According to the present invention, network intermediate devices are provided for a network having a plurality of local area network (xe2x80x9cLANxe2x80x9d) segments. The devices comprise a plurality of ports coupled to LAN segments in the network. Topology management resources on the devices manage the plurality of ports according to a spanning tree algorithm, in order to set an active topology for the plurality of ports. The topology management resources include memory which stores parameters specifying the active topology. The parameters include an identification of a root of the network, an identification of a port in the plurality of ports for a root port role to be used for a path to the root, an identification of one or more ports in the plurality of ports for designated port roles to be used for paths between the root and the respective LAN segments coupled to the one or more ports, and an identification of one or more ports in the plurality of ports for alternate port roles (for example, by being neither a root nor designated port role). Logic in the topology management resources computes states for the ports in the plurality of ports in response to the parameters. This logic places the port in the root port role into a forwarding state, places the one or more ports in the designated port roles into a forwarding state, and places the one or more ports in the alternate port roles into a blocking state. In addition, logic is provided to manage the transition of the states of the ports in the plurality of ports in response to a change in the active topology. For a port changing from the alternate port role to a designated port role, the logic causes a transition from the blocking state to a transitional state, such as a state involving the listening and learning processes of the 802.1D standard. Upon satisfaction of a condition of the transitional state, the logic causes a transition to the forwarding state. Upon an event causing a topology change resulting in a particular port changing from the candidate root port role to the root port role and in the previous root port changing to the designated port role, the process allows the previous root port to enter into the forwarding state without requiring transition through the listening and forwarding states. Qualification as a suitable candidate root port is based upon propagating a message from the root bridge, such as a BPDU message, which carries the identifier of the port on the root bridge from which the message originates. Logic in the bridges is able to identify the branch of the tree from which the message originates, and to select the candidate root port in response to the branch information. Thus, the port on a branch other than the root is a suitable candidate root port. A port on the same branch as the root is suitable if it has recently received (such as within one Hello time in the standard spanning tree) updated configuration information from its upstream bridge (designated bridge on the port), such as by a configuration BPDU. Thus, in the case of a suitable alternate port changing to the root port role, the previously root port changing to the designated port role may transition immediately into a forwarding state without going through transitional stages, and without forming a loop.
Accordingly, the present invention provides enhancements to the spanning tree protocol based on identifying port roles including the root port role, the designated port role, an alternate port role, and, in shared media networks, a backup port role. Transitions from the blocking state to the forwarding state, and from the forwarding state to the blocking state, depend upon the particular role of the port.
Other aspects and advantages of the present invention are shown by the figures, the detailed description, and the claims which follow.